# encoding:utf-8

import sys
import csv
import copy
import datetime

start_time = datetime.datetime.now()

# one的区别：将连续移动视为1步


# 读取MAP文件并解析到序列中【形状、目标】
# TODO：MAP文件改为调用系统选择框
# TODO：自动解析文件encoding
target_count = 0
shape_count = 0
target = []
shape = []
map_file = open('in\\map.txt', mode='r', encoding='utf-8')
map_reader = csv.reader(map_file, delimiter=':')
for row in map_reader:
    if row[0] == 's':
        # 格式检查
        if len(row) != 3:
            print('形状行格式错误')
            sys.exit(1)
        # 填充形状序列
        shape_count += 1
        shape.append([shape_count, eval(row[1]), eval(row[2])])
    elif row[0] == 't':
        # 格式检查
        target_count += 1
        # 记录目标行
        for i in range(1, len(row)):
            target.append(eval(row[i]))
    else:
        # 格式检查
        print("不可识别的行")
        sys.exit(1)
map_file.close()
# 格式检查
if target_count != 1:
    print("目标行数不为1")
    sys.exit(1)
if len(target) == 0:
    print("无目标")
    sys.exit(1)


# 打印map图形
def print_matrix(t):
    for i in t:
        print(i)
    print('')


# check point - 打印解析形状
print('共 {} 个形状'.format(len(shape)))
print_matrix(shape)
print('共 {} 个目标'.format(len(target)))
print_matrix(target)

# 从【形状】列表中生成MAP
row = 0
column = 0
for i in shape:
    for j in i[2]:
        row = max(row, j[0])
        column = max(column, j[1])
map_list = [[0 for c in range(column)] for r in range(row)]
for i in shape:
    for j in i[2]:
        map_list[j[0] - 1][j[1] - 1] = i[0]

# 目标坐标修正
target_init_shape = copy.deepcopy(target)
target_init_shape = [x[0] for x in target_init_shape]
for i in range(len(target)):
    target[i][0][0] -= 1
    target[i][0][1] -= 1
    target[i][1][0] -= 1
    target[i][1][1] -= 1

# check point - 打印map
print('当前MAP')
print_matrix(map_list)
print('')

# 比较目标当前位置与最终位置
target_init = [x[0] for x in target]
target_final = [x[1] for x in target]


# 检查目标达成
def check_target(t):
    if t == target_final:
        return True
    else:
        return False


# 广搜核心程序
# 广搜数据结构：
# 本级指针(index),[上级指针,map,目标位置,总步数,|简化MAP|,[图形编号,移动方向]]
# 广搜思路：
# 1 尝试所有可能移动：每个shape 及 所有可能的连续多步移动
#   1.1 检查是否达成目标
#       达成：结束，回溯指针出解
#   1.2 检查是否与历史重复
# 2 与历史不重复，列表+1
# 3 尝试下一个


# 检查所有方向上可移动的步数
def cal_move(sh, map_d):
    step_list = []
    for i in sh[1]:
        if i[0] == 1:  # 向上移动
            max_move = -1
            for r in range(len(map_d)):
                if max_move == 0:
                    break
                for c in range(len(map_d[0])):
                    if max_move == 0:
                        break
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, r + 1):
                            if map_d[r - m][c] == 0 or map_d[r - m][c] == sh[0]:
                                e_move = m
                            else:
                                break
                        if max_move == -1:
                            max_move = e_move
                        else:
                            max_move = min(max_move, e_move)
            if max_move != 0:
                if i[1] == -1:
                    step_list.append([i[0], max_move])
                else:
                    step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 2:  # 向下移动
            max_move = -1
            for r in range(len(map_d)):
                if max_move == 0:
                    break
                for c in range(len(map_d[0])):
                    if max_move == 0:
                        break
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, len(map_d) - r):
                            if map_d[r + m][c] == 0 or map_d[r + m][c] == sh[0]:
                                e_move = m
                            else:
                                break
                        if max_move == -1:
                            max_move = e_move
                        else:
                            max_move = min(max_move, e_move)
            if max_move != 0:
                if i[1] == -1:
                    step_list.append([i[0], max_move])
                else:
                    step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 3:  # 向左移动
            max_move = -1
            for r in range(len(map_d)):
                if max_move == 0:
                    break
                for c in range(len(map_d[0])):
                    if max_move == 0:
                        break
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, c + 1):
                            if map_d[r][c - m] == 0 or map_d[r][c - m] == sh[0]:
                                e_move = m
                            else:
                                break
                        if max_move == -1:
                            max_move = e_move
                        else:
                            max_move = min(max_move, e_move)
            if max_move != 0:
                if i[1] == -1:
                    step_list.append([i[0], max_move])
                else:
                    step_list.append([i[0], min(i[1], max_move)])
        elif i[0] == 4:  # 向右移动
            max_move = -1
            for r in range(len(map_d)):
                if max_move == 0:
                    break
                for c in range(len(map_d[0])):
                    if max_move == 0:
                        break
                    if map_d[r][c] == sh[0]:
                        e_move = 0
                        for m in range(1, len(map_d[0]) - c):
                            if map_d[r][c + m] == 0 or map_d[r][c + m] == sh[0]:
                                e_move = m
                            else:
                                break
                        if max_move == -1:
                            max_move = e_move
                        else:
                            max_move = min(max_move, e_move)
            if max_move != 0:
                if i[1] == -1:
                    step_list.append([i[0], max_move])
                else:
                    step_list.append([i[0], min(i[1], max_move)])
    return step_list


# 检查是否与历史重复
# 排除相同图形
def simple_shape(t):
    # 最简化图形
    t_copy = copy.deepcopy(t)
    r_s = t_copy[0][0]
    c_s = t_copy[0][1]
    for i in t_copy[1:]:
        r_s = min(r_s, i[0])
        c_s = min(c_s, i[1])
    for i in t_copy:
        i[0] = i[0] - r_s
        i[1] = i[1] - c_s
    return t_copy


# 记录所有图形对应关系
# 数据结构：[最简化图形,图形编号,[相同图形编号]]
shape_same = []
for i in shape:
    p = False  # 是否目标图形?
    for j in target_init_shape:
        if j in i[2]:
            p = True
            break
    if p:
        continue
    simp_s = simple_shape(i[2])
    p = True  # 不存在相似图形？
    for j in shape_same:
        if simp_s == j[0]:
            p = False  # 找到追加相似
            j[2].append(i[0])
            break
    if p:  # 没找到追加新图形
        shape_same.append([simp_s, i[0], []])


# for i in shape: # 目标图形不需要放进去
#     for j in target_init_shape:
#         if j in i[2]:
#             shape_same.append(['target', i[0], []])
#             break


# 检查是否与历史重复
def check_history(t):  # 返回重复图形编号,无重复返回 -1
    for i in range(len(map_history) - 1, -1, -1):
        if t == map_history[i][4]:
            return i
    return -1


def simp_map(t):
    # 简化MAP-相同图形处理
    t_c = copy.deepcopy(t)
    for a in t_c:
        for b in range(len(a)):
            for c in shape_same:
                if a[b] in c[2]:
                    a[b] = c[1]
                    break
    return t_c


# 广搜数据结构：
# 本级指针(index),[上级指针,map,目标位置,总步数,|简化MAP|,[图形编号,移动方向、步数]]
map_history = [[-1, map_list, target_init, 0, simp_map(map_list), [0, '']]]

direction_dic = {1: '上', 2: '下', 3: '左', 4: '右'}

# 求解优化-shape排序:优先移动目标图形，然后移动大图形，然后小图形
shape.sort(key=lambda sh: len(sh[2]), reverse=True)
for i in range(len(shape)):
    for j in target_init_shape:
        if j in shape[i][2]:
            shape.insert(0, shape[i])
            shape.pop(i + 1)
            continue


# testcount = 0


# 对单个图形进行递归连续移动
# i_append_list = []  # 格式：[[map_now,target_now,move_describe]]
def find_moves(mi, ti, sh, move_list, move_describe=""):
    # todo
    # global testcount
    # testcount += 1
    # print("递归次数 {}".format(testcount))
    # print("当前shape {}".format(sh[0]))
    # print_matrix(mi)
    # todo
    md_init = move_describe
    steps = cal_move(sh, mi)
    for j in steps:
        if j[0] == 1 and j[1] != 0:  # 向上移动
            map_copy = copy.deepcopy(mi)
            target_copy = copy.deepcopy(ti)
            for c in range(len(map_copy[0])):
                for r in range(len(map_copy)):
                    if map_copy[r][c] == sh[0]:
                        map_copy[r - j[1]][c] = sh[0]
                        map_copy[r][c] = 0
                        for tn in range(len(target_copy)):
                            if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                target_copy[tn][0] -= j[1]
            if not (map_copy in [x[0] for x in move_list]):
                move_describe = md_init
                if len(move_describe) == 0:
                    move_describe = direction_dic[j[0]] + str(j[1])
                elif move_describe[-2] == direction_dic[j[0]]:
                    move_describe = move_describe[:-1] + str(int(move_describe[-1]) + j[1])
                else:
                    move_describe = move_describe + direction_dic[j[0]] + str(j[1])
                move_list.append([map_copy, target_copy, move_describe])
                find_moves(map_copy, target_copy, sh, move_list, move_describe)
        elif j[0] == 2 and j[1] != 0:  # 向下移动
            map_copy = copy.deepcopy(mi)
            target_copy = copy.deepcopy(ti)
            for c in range(len(map_copy[0])):
                for r in range(len(map_copy) - 1, -1, -1):
                    if map_copy[r][c] == sh[0]:
                        map_copy[r + j[1]][c] = sh[0]
                        map_copy[r][c] = 0
                        for tn in range(len(target_copy)):
                            if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                target_copy[tn][0] += j[1]
            if not (map_copy in [x[0] for x in move_list]):
                move_describe = md_init
                if len(move_describe) == 0:
                    move_describe = direction_dic[j[0]] + str(j[1])
                elif move_describe[-2] == direction_dic[j[0]]:
                    move_describe = move_describe[:-1] + str(int(move_describe[-1]) + j[1])
                else:
                    move_describe = move_describe + direction_dic[j[0]] + str(j[1])
                move_list.append([map_copy, target_copy, move_describe])
                find_moves(map_copy, target_copy, sh, move_list, move_describe)
        elif j[0] == 3 and j[1] != 0:  # 向左移动
            map_copy = copy.deepcopy(mi)
            target_copy = copy.deepcopy(ti)
            for r in range(len(map_copy)):
                for c in range(len(map_copy[0])):
                    if map_copy[r][c] == sh[0]:
                        map_copy[r][c - j[1]] = sh[0]
                        map_copy[r][c] = 0
                        for tn in range(len(target_copy)):
                            if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                target_copy[tn][1] -= j[1]
            if not (map_copy in [x[0] for x in move_list]):
                move_describe = md_init
                if len(move_describe) == 0:
                    move_describe = direction_dic[j[0]] + str(j[1])
                elif move_describe[-2] == direction_dic[j[0]]:
                    move_describe = move_describe[:-1] + str(int(move_describe[-1]) + j[1])
                else:
                    move_describe = move_describe + direction_dic[j[0]] + str(j[1])
                move_list.append([map_copy, target_copy, move_describe])
                find_moves(map_copy, target_copy, sh, move_list, move_describe)
        elif j[0] == 4 and j[1] != 0:  # 向右移动
            map_copy = copy.deepcopy(mi)
            target_copy = copy.deepcopy(ti)
            # todo
            # print('一轮输出')
            # print_matrix(map_copy)
            # print(j)
            # print(sh)
            # todo
            for r in range(len(map_copy)):
                for c in range(len(map_copy[0]) - 1, -1, -1):
                    if map_copy[r][c] == sh[0]:
                        map_copy[r][c + j[1]] = sh[0]
                        map_copy[r][c] = 0
                        for tn in range(len(target_copy)):
                            if target_copy[tn][0] == r and target_copy[tn][1] == c:
                                target_copy[tn][1] += j[1]
            if not (map_copy in [x[0] for x in move_list]):
                move_describe = md_init
                if len(move_describe) == 0:
                    move_describe = direction_dic[j[0]] + str(j[1])
                elif move_describe[-2] == direction_dic[j[0]]:
                    move_describe = move_describe[:-1] + str(int(move_describe[-1]) + j[1])
                else:
                    move_describe = move_describe + direction_dic[j[0]] + str(j[1])
                move_list.append([map_copy, target_copy, move_describe])
                find_moves(map_copy, target_copy, sh, move_list, move_describe)


# 求解核心
# 广搜核心程序
# 广搜数据结构：
# 本级指针(index),[上级指针,map,目标位置,总步数,|简化MAP|,[图形编号,移动方向]]
# 广搜思路：
# 1 尝试所有可能移动：每个shape 及 所有可能的连续多步移动
#   1.1 检查是否达成目标
#       达成：结束，回溯指针出解
#   1.2 检查是否与历史重复
# 2 与历史不重复，列表+1
# 3 尝试下一个
current = 0
p_find = False
solution_index = 0
while current < len(map_history) and not p_find:
    if current % 1000 == 0:
        print('第 {} 次循环，第 {} 步'.format(current, map_history[current][3]))
    # todo 测试
    # print('第 {} 次循环，第 {} 步，父节点 {}'.format(current, map_history[current][3], map_history[current][0]))
    # print_map(map_history[current][1])
    # if current == 5548:
    #     print_map(map_history)
    #     sys.exit(0)
    # 以上部分为测试
    for i in shape:  # 每个形状
        # 格式：[[map_now,target_now,move_describe]]
        i_append_list = [[map_history[current][1], map_history[current][2], '']]
        find_moves(map_history[current][1], map_history[current][2], i, i_append_list, move_describe="")
        for j in range(1, len(i_append_list)):

            map_copy_s = simp_map(i_append_list[j][0])
            if check_history(map_copy_s) == -1:
                map_history.append(
                    [current, i_append_list[j][0], i_append_list[j][1], map_history[current][3] + 1, map_copy_s,
                     [i[0], i_append_list[j][2]]])
                if check_target(i_append_list[j][1]):
                    # if i_append_list[j][1] == target_final: # 无效优化，不提升速度
                    p_find = True
                    if solution_index == 0:
                        solution_index = len(map_history) - 1

    current = current + 1

# 求不出解
if current == len(map_history):
    print('无解')
    sys.exit(0)

# 追溯步骤
map_trace = []
while solution_index != -1:
    map_trace.insert(0, map_history[solution_index])
    solution_index = map_history[solution_index][0]

# 打印求解过程程序-打印 MAP 、 移动图形 和 方向、步数
for i in map_trace:
    print('第 {} 步：图形 {} 移动 {}'.format(i[3], i[5][0], i[5][1]))
    print_matrix(i[1])
print('\n总共 {} 次循环'.format(current))
print('最短 {} 步\n'.format(len(map_trace) - 1))
end_time = datetime.datetime.now()

print('总耗时： {}'.format(end_time - start_time))
